/*
选择排序
编写人：loulu
日期：2023-1-10
版本：v1.0
变化历史： 
改用 gitee记录代码变化

*/

#define WINDOWS_OS 
//#define DEBUG_print
//#define PRINT_loop



#include <bits/stdc++.h>

#ifdef WINDOWS_OS
#include<windows.h>
#endif



using namespace std;

//自定义交换函数
void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
//自定义的输出函数disp
void disp(int a[],int n) //输出a中所有元素
{ int i;
	for (i=0;i<n;i++)
		printf("%d ",a[i]);
	printf("\n");
}

////随机生成一组不重复的一维数据的自定义函数 
std::vector<int> randVector(int num) {
	std::vector<int> result;
	result.clear();
	result.reserve(num);
	srand((int)time(0)); //利用当前机器时间产生随机数，
	for (int i = 0; i < num; i++)
	{
		result.push_back(i);
	}
	int p1;
	int p2;
	int temp;
	//int count = num;
	
	while (--num)
	{
		p1 = num;
		p2 = rand() % num;
		temp = result[p1];
		result[p1] = result[p2];
		result[p2] = temp;
	}
	return result;
}

//随机生成一组允许重复的一维数据的函数
std::vector<int> randVector2(int num) {
	std::vector<int> result;
	result.clear(); 
    srand(time(NULL)); // 随机种子
	int t;
    for (int i = 0; i < num; i++){
        t = rand() % num ;
        result.push_back(t);
    }
	return result;
}


//冒泡排序
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
    {
       for (j = 0; j < len - 1 - i; j++)
		{
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
		}
		#ifdef PRINT_loop
		disp(arr, len);
		#endif
	}

}
//改进冒泡排序，增加一个flag标志，用来确定是否存在交换，不存在交换，
//说明已经是有序的，提前结束循环
void bubble_sort2(int arr[], int len) {
	int i, j, temp;
	for (i = 0; i < len - 1; i++){
		bool flag=false;
		for (j = 0; j < len - 1 - i; j++){
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag=true;
			}
		}
		#ifdef PRINT_loop
	 	  disp(arr, len);
		#endif
		if(!flag)return;
	}
}

//选择排序
void  select_sort(int arr[], int  len) {
      int i,j;
      for (i = 0 ; i < len - 1 ; i++)
      {
        int min =   i;
        for (j = i + 1; j < len; j++)     //走访未排序的元素
        {    
			if (arr[j] < arr[min])    //找到目前最小值 
            {    min = j;    //记录最小值
			}
        }  //之前if没有花括号，有bug
		swap(&arr[min], &arr[i]);    //做交换
		#ifdef PRINT_loop
		   disp(arr, len);
		#endif
      } 
  
}
//插入排序
void insertion_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++)
		{
                key = arr[i];
                j=i-1;
                while((j>=0) && (arr[j]>key)) {
                        arr[j+1] = arr[j];
                        j--;
                }
                arr[j+1] = key;
	       #ifdef PRINT_loop
		     disp(arr, len);
		   #endif
		}
}

//希尔排序， bug消除！！！！
void shell_sort(int arr[], int len)
 {
        int gap, i, j;
        int temp;
        for (gap = len >> 1; gap > 0; gap >>= 1)
		{
                for (i = gap; i < len; i++) 
				{
                        temp = arr[i];
                        for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                        {
						    arr[j + gap] = arr[j];
						}
	                    arr[j + gap] = temp;
						
                }
		}
}

//归并排序，递推法
void merge_sort1(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

//归并排序，递归法
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort2(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}
//---------------------------------




//快速排序,递推法 
//------------------------------------
typedef struct _Range {
    int start, end;
} Range;

Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}

/*void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}*/

void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負值時引發段錯誤（Segment Fault）
    // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
        int left = range.start, right = range.end;
        do {
            while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求
            while (arr[right] > mid) --right; //檢測基準點右側是否符合要求
            if (left <= right) {
                swap(&arr[left], &arr[right]);
                left++;
                right--;               // 移動指針以繼續
            }
        } while (left <= right);
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}


//快速排序，递推法

void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}

void quick_sort2(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

//堆排序
void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    int i;
    // 初始化，i從最後一個父節點開始調整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
//-------------------

//计数排序
void counting_sort(int *ini_arr, int *sorted_arr, int n) {
        int *count_arr = (int *) malloc(sizeof(int) * 100*n);//假设每个数最多重复100次
        int i, j, k;
        for (k = 0; k < 100*n; k++)
        {        count_arr[k] = 0;
		}
        for (i = 0; i < n; i++)
        {        count_arr[ini_arr[i]]++;
		}        
		for (k = 1; k < 100*n; k++)
        {        count_arr[k] += count_arr[k - 1];
        }
		for (j = n; j > 0; j--)
        {        sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
		}        
		free(count_arr);
}



int main() {
    //原始待排序数据准备
    //int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    //int len = (int) sizeof(arr) / sizeof(*arr);
	int n=2000; int a[n]={0}; int a_sorted[n]={0};

	vector v=randVector2(n); //生成n个可重复的随机数，顺序是随机的
//	vector v={4,0,1,2,3};

#ifdef WINDOWS_OS
	double run_time;
	_LARGE_INTEGER time_start;	//开始时间
	_LARGE_INTEGER time_over;	//结束时间
	double dqFreq;		//计时器频率
	LARGE_INTEGER f;	//计时器频率
#else
	clock_t start_time,end_time;
#endif


	
copy(v.begin(),v.end(), a);
copy(v.begin(),v.end(), a_sorted);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    counting_sort(a,a_sorted,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n计数排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"计数排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
//	#ifdef DEBUG_print 
		printf("计数排序后:"); disp(a_sorted,n);
//    #endif




	copy(v.begin(),v.end(), a);    
    //待排序数据显示
	printf("排序前:"); disp(a,n);

//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    bubble_sort(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n冒泡排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"冒泡排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("冒泡排序后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    bubble_sort2(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n改进冒泡windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"改进冒泡排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("改进冒泡排序后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    select_sort(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n选择排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"选择排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("选择排序后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    insertion_sort(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n插入排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"插入排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print
		printf("插入排序后:"); disp(a,n);
	#endif



copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    shell_sort(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n希尔排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"希尔排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("希尔排序后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    merge_sort1(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n归并(递推)排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"归并排序(递推)花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("归并排序(递推)后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    merge_sort2(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n归并(递归)排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"归并排序(递归)花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("归并排序(递归)后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    quick_sort(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n快速(递推)排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"快速排序(递推)花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print	
		printf("快速排序(递推)后:"); disp(a,n);
	#endif

copy(v.begin(),v.end(), a);
//开启定时
//----------------------
#ifdef WINDOWS_OS
	QueryPerformanceFrequency(&f);  //windows 系统API函数
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
//-----------------------
#else
	start_time=clock();
#endif

    //执行排序
    heap_sort(a,n);


#ifdef WINDOWS_OS
//---------------计时结束，输出时间差----
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\n堆排序windows下运行时间：%fus\n",run_time);
//-------------------------------------------------
#else
	end_time=clock();
	cout<<"堆排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
#endif
    //显示已排序数据
	#ifdef DEBUG_print 
		printf("堆排序后:"); disp(a,n);
    #endif




/*	copy(v.begin(),v.end(), a); 
	start_time=clock();
    //执行排序
    bubble_sort2(a,n);

	end_time=clock();
	cout<<"改进冒泡排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";

	start_time=clock();

	copy(v.begin(),v.end(), a); 
    //执行排序
    select_sort(a,n);

	end_time=clock();
	cout<<"选择排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";

	copy(v.begin(),v.end(), a); 
	start_time=clock();
    //执行排序
    insertion_sort(a,n);

	end_time=clock();
	cout<<"插入排序花费的时间为:"<<(double(end_time-start_time)/CLOCKS_PER_SEC)<<"s\n";
*/

    //显示已排序数据
	//printf("排序后:"); disp(a,n);

    return 0;
}

